package q437_pathSum;

import CommonClass.Common.TreeNode;

public class Solution_1 {
    /*
    这种方法涉及到一种双重dfs的方式
    也就是两个方法都会调用自己
    由于每个路径都是截取了树中的一段 所以每次到达一个新节点的时候都应有一个重新统计的sum
    因此dfs中每次都是调用check(root, 0); 然后check函数中再进行路径和的统计
     */
    int ans, targetSum;
    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        ans = 0;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        check(root, 0);
        dfs(root.left);
        dfs(root.right);
    }

    private void check(TreeNode root, int sum) {
        sum += root.val;
        if (sum == targetSum) ++ans;
        check(root.right, sum);
        check(root.left, sum);
    }
}
